// include/bigintaddsub.h
#pragma once

#include <algorithm>
#include <iostream>
#include <string>

class BigInt {
public:
    BigInt() : digits_("0"), isNegative_(false) {}

    explicit BigInt(const std::string& value) {
        parse(value);
    }

    explicit BigInt(long long value) {
        if (value < 0) {
            isNegative_ = true;
            value = -value;
        } else {
            isNegative_ = false;
        }
        digits_ = std::to_string(value);
        normalizeZero();
    }

    std::string toString() const {
        return (isNegative_ && digits_ != "0") ? "-" + digits_ : digits_;
    }

    friend std::ostream& operator<<(std::ostream& os, const BigInt& obj) {
        os << obj.toString();
        return os;
    }

    friend BigInt operator+(const BigInt& lhs, const BigInt& rhs) {
        if (lhs.isNegative_ == rhs.isNegative_) {
            BigInt result;
            result.digits_ = addAbsolute(lhs.digits_, rhs.digits_);
            result.isNegative_ = lhs.isNegative_;
            result.normalizeZero();
            return result;
        }

        if (compareAbsolute(lhs.digits_, rhs.digits_) >= 0) {
            BigInt result;
            result.digits_ = subtractAbsolute(lhs.digits_, rhs.digits_);
            result.isNegative_ = lhs.isNegative_;
            result.normalizeZero();
            return result;
        } else {
            BigInt result;
            result.digits_ = subtractAbsolute(rhs.digits_, lhs.digits_);
            result.isNegative_ = rhs.isNegative_;
            result.normalizeZero();
            return result;
        }
    }

    friend BigInt operator-(const BigInt& lhs, const BigInt& rhs) {
        BigInt negated = rhs;
        negated.isNegative_ = !rhs.isNegative_;
        return lhs + negated;
    }

private:
    std::string digits_;
    bool isNegative_{false};

    // Step7: 允许跳过多余符号并忽略非数字字符
    void parse(const std::string& value) {
        if (value.empty()) {
            digits_ = "0";
            isNegative_ = false;
            return;
        }

        std::size_t index = 0;
        bool signFound = false;
        for (; index < value.size(); ++index) {
            char c = value[index];
            if (!signFound && (c == '+' || c == '-')) {
                isNegative_ = (c == '-');
                signFound = true;
            } else if (c >= '0' && c <= '9') {
                break;
            }
        }

        digits_.clear();
        for (; index < value.size(); ++index) {
            char c = value[index];
            if (c >= '0' && c <= '9') {
                digits_.push_back(c);
            }
        }

        if (digits_.empty()) {
            digits_ = "0";
            isNegative_ = false;
        } else {
            removeLeadingZeros();
        }

        normalizeZero();
    }

    void removeLeadingZeros() {
        auto it = digits_.begin();
        while (it != digits_.end() - 1 && *it == '0') {
            ++it;
        }
        digits_.erase(digits_.begin(), it);
    }

    void normalizeZero() {
        if (digits_ == "0") {
            isNegative_ = false;
        }
    }

    static std::string addAbsolute(const std::string& lhs, const std::string& rhs) {
        int i = static_cast<int>(lhs.size()) - 1;
        int j = static_cast<int>(rhs.size()) - 1;

        std::string result;
        result.reserve(std::max(lhs.size(), rhs.size()) + 1);

        bool carry = false;
        while (i >= 0 || j >= 0) {
            int sum = (carry ? 1 : 0);
            if (i >= 0) {
                sum += lhs[i] - '0';
                --i;
            }
            if (j >= 0) {
                sum += rhs[j] - '0';
                --j;
            }

            if (sum >= 10) {
                sum -= 10;
                carry = true;
            } else {
                carry = false;
            }

            result.push_back(static_cast<char>('0' + sum));
        }

        if (carry) {
            result.push_back('1');
        }

        std::reverse(result.begin(), result.end());
        return result;
    }

    static std::string subtractAbsolute(const std::string& lhs, const std::string& rhs) {
        int i = static_cast<int>(lhs.size()) - 1;
        int j = static_cast<int>(rhs.size()) - 1;

        std::string result;
        result.reserve(lhs.size());

        bool borrow = false;
        while (i >= 0) {
            int diff = lhs[i] - '0' - (borrow ? 1 : 0);
            --i;

            if (j >= 0) {
                diff -= (rhs[j] - '0');
                --j;
            }

            if (diff < 0) {
                diff += 10;
                borrow = true;
            } else {
                borrow = false;
            }

            result.push_back(static_cast<char>('0' + diff));
        }

        while (result.size() > 1 && result.back() == '0') {
            result.pop_back();
        }

        std::reverse(result.begin(), result.end());
        return result;
    }

    static int compareAbsolute(const std::string& lhs, const std::string& rhs) {
        if (lhs.size() != rhs.size()) {
            return (lhs.size() > rhs.size()) ? 1 : -1;
        }
        if (lhs == rhs) {
            return 0;
        }
        return (lhs > rhs) ? 1 : -1;
    }
};